<!DOCTYPE html>
<html lang="">
    <head><meta charset='utf-8'>
<meta name='viewport' content='width=device-width, initial-scale=1'>
<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js">
</script><meta name='description' content='一、什么是排序算法 ​	所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。
二、排序的稳定性 在了解排序算法之前，我们先了解下排序的稳定性： 所谓的排序稳定性是指在排序的前后，元素的相对次序是否发生改变。若相对次序发生改变，那么证明该排序算法是不稳定的。 举个🌰，数组a的值为[1,5,3,5,4]，我们可以看到排序前加粗的5排在前一个未加粗的5后面，经过某种排序算法后数组a的值为[1,3,4,5,5]，此时加粗的5排在了未加粗的5前面，这样元素的相对次序就发生了改变，所以这种排序算法的稳定性就是不稳定的。
三、基础的排序算法 1.冒泡排序 ​	冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。简单来说就是元素间两两相比较，当比对到数组中最后一个元素时，最大|最小的元素就落到数组中最后一个位置，再不断的重复此过程最终数组就变得有序了。
动图演示 (点击查看)
 
代码实现 先定义一个用于交换的方法，以便复用：
public static void swap(int[] nums,int i,int j){ int temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } 冒泡排序：
//冒泡排序,时间复杂度O(n²),具有稳定性  public static void bubbleSort(int[] nums){ int len=nums.length-1; for (int i=len;i&amp;gt;0;i--){ for (int j = 0; j &amp;lt;i ; j&#43;&#43;) { if (nums[j]&amp;gt;nums[j&#43;1]){ swap(nums,j,j&#43;1); } } } } 冒泡排序的时间复杂度为O(n²)，又因为再对比时相等的值不会交换，所以具有稳定性。
2.选择排序 算法描述 ​	选择排序是一种简单直观的排序算法，它也是一种交换排序算法，和冒泡排序有一定的相似度，可以认为选择排序是冒泡排序的一种改进。选择排序的原理就是：从未排序的数组中找到数组中的最大（小）值，放到未排序数组的起始位置，重复此过程最终整个数组就变成了一个有序数组。
动图演示 (点击查看)
 
代码实现 //选择排序,时间复杂度O(n²),不具有稳定性  public static void selectSort(int[] nums){ int len=nums.'><title>排序算法（一）</title>

<link rel='canonical' href='http://example.org/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/'>

<link rel="stylesheet" href="/scss/style.min.css"><meta property='og:title' content='排序算法（一）'>
<meta property='og:description' content='一、什么是排序算法 ​	所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。
二、排序的稳定性 在了解排序算法之前，我们先了解下排序的稳定性： 所谓的排序稳定性是指在排序的前后，元素的相对次序是否发生改变。若相对次序发生改变，那么证明该排序算法是不稳定的。 举个🌰，数组a的值为[1,5,3,5,4]，我们可以看到排序前加粗的5排在前一个未加粗的5后面，经过某种排序算法后数组a的值为[1,3,4,5,5]，此时加粗的5排在了未加粗的5前面，这样元素的相对次序就发生了改变，所以这种排序算法的稳定性就是不稳定的。
三、基础的排序算法 1.冒泡排序 ​	冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。简单来说就是元素间两两相比较，当比对到数组中最后一个元素时，最大|最小的元素就落到数组中最后一个位置，再不断的重复此过程最终数组就变得有序了。
动图演示 (点击查看)
 
代码实现 先定义一个用于交换的方法，以便复用：
public static void swap(int[] nums,int i,int j){ int temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } 冒泡排序：
//冒泡排序,时间复杂度O(n²),具有稳定性  public static void bubbleSort(int[] nums){ int len=nums.length-1; for (int i=len;i&amp;gt;0;i--){ for (int j = 0; j &amp;lt;i ; j&#43;&#43;) { if (nums[j]&amp;gt;nums[j&#43;1]){ swap(nums,j,j&#43;1); } } } } 冒泡排序的时间复杂度为O(n²)，又因为再对比时相等的值不会交换，所以具有稳定性。
2.选择排序 算法描述 ​	选择排序是一种简单直观的排序算法，它也是一种交换排序算法，和冒泡排序有一定的相似度，可以认为选择排序是冒泡排序的一种改进。选择排序的原理就是：从未排序的数组中找到数组中的最大（小）值，放到未排序数组的起始位置，重复此过程最终整个数组就变成了一个有序数组。
动图演示 (点击查看)
 
代码实现 //选择排序,时间复杂度O(n²),不具有稳定性  public static void selectSort(int[] nums){ int len=nums.'>
<meta property='og:url' content='http://example.org/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/'>
<meta property='og:site_name' content='我的技术小屋'>
<meta property='og:type' content='article'><meta property='article:section' content='Post' /><meta property='article:tag' content='排序算法' /><meta property='article:published_time' content='2022-01-10T00:00:00&#43;00:00'/><meta property='article:modified_time' content='2022-01-10T00:00:00&#43;00:00'/><meta property='og:image' content='http://example.org/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/aa.jfif' />
<meta name="twitter:title" content="排序算法（一）">
<meta name="twitter:description" content="一、什么是排序算法 ​	所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。
二、排序的稳定性 在了解排序算法之前，我们先了解下排序的稳定性： 所谓的排序稳定性是指在排序的前后，元素的相对次序是否发生改变。若相对次序发生改变，那么证明该排序算法是不稳定的。 举个🌰，数组a的值为[1,5,3,5,4]，我们可以看到排序前加粗的5排在前一个未加粗的5后面，经过某种排序算法后数组a的值为[1,3,4,5,5]，此时加粗的5排在了未加粗的5前面，这样元素的相对次序就发生了改变，所以这种排序算法的稳定性就是不稳定的。
三、基础的排序算法 1.冒泡排序 ​	冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。简单来说就是元素间两两相比较，当比对到数组中最后一个元素时，最大|最小的元素就落到数组中最后一个位置，再不断的重复此过程最终数组就变得有序了。
动图演示 (点击查看)
 
代码实现 先定义一个用于交换的方法，以便复用：
public static void swap(int[] nums,int i,int j){ int temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } 冒泡排序：
//冒泡排序,时间复杂度O(n²),具有稳定性  public static void bubbleSort(int[] nums){ int len=nums.length-1; for (int i=len;i&amp;gt;0;i--){ for (int j = 0; j &amp;lt;i ; j&#43;&#43;) { if (nums[j]&amp;gt;nums[j&#43;1]){ swap(nums,j,j&#43;1); } } } } 冒泡排序的时间复杂度为O(n²)，又因为再对比时相等的值不会交换，所以具有稳定性。
2.选择排序 算法描述 ​	选择排序是一种简单直观的排序算法，它也是一种交换排序算法，和冒泡排序有一定的相似度，可以认为选择排序是冒泡排序的一种改进。选择排序的原理就是：从未排序的数组中找到数组中的最大（小）值，放到未排序数组的起始位置，重复此过程最终整个数组就变成了一个有序数组。
动图演示 (点击查看)
 
代码实现 //选择排序,时间复杂度O(n²),不具有稳定性  public static void selectSort(int[] nums){ int len=nums."><meta name="twitter:card" content="summary_large_image">
    <meta name="twitter:image" content='http://example.org/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/aa.jfif' />
    <link rel="shortcut icon" href="/img/%e7%bc%85%e5%9b%a0%e7%8c%ab.png" />
<style>
    :root {
        --article-font-family: "Noto Serif SC", var(--base-font-family);
    }
</style>

<script> 
		(function () {
		    const customFont = document.createElement('link');
		    customFont.href = "https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@300;700&display=swap"; 
		    customFont.type = "text/css";
		    customFont.rel = "stylesheet";
		
		    document.head.appendChild(customFont);
		}());
</script>
    </head>
    <body class="
    article-page has-toc
">
    <script>
        (function() {
            const colorSchemeKey = 'StackColorScheme';
            if(!localStorage.getItem(colorSchemeKey)){
                localStorage.setItem(colorSchemeKey, "auto");
            }
        })();
    </script><script>
    (function() {
        const colorSchemeKey = 'StackColorScheme';
        const colorSchemeItem = localStorage.getItem(colorSchemeKey);
        const supportDarkMode = window.matchMedia('(prefers-color-scheme: dark)').matches === true;

        if (colorSchemeItem == 'dark' || colorSchemeItem === 'auto' && supportDarkMode) {
            

            document.documentElement.dataset.scheme = 'dark';
        } else {
            document.documentElement.dataset.scheme = 'light';
        }
    })();
</script>
<div class="container main-container flex 
    
        extended
    
">
    
        <div id="article-toolbar">
            <a href="/" class="back-home">
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-chevron-left" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <polyline points="15 6 9 12 15 18" />
</svg>



                <span>Back</span>
            </a>
        </div>
    
<main class="main full-width">
    <article class="has-image main-article">
    <header class="article-header">
        <div class="article-image">
            <a href="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/">
                <img src="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/aa_huc032c4d09cfc3260a681c94ccd0382c2_189778_800x0_resize_q75_box.jfif"
                        srcset="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/aa_huc032c4d09cfc3260a681c94ccd0382c2_189778_800x0_resize_q75_box.jfif 800w, /post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/aa_huc032c4d09cfc3260a681c94ccd0382c2_189778_1600x0_resize_q75_box.jfif 1600w"
                        width="800" 
                        height="450" 
                        loading="lazy"
                        alt="Featured image of post 排序算法（一）" />
                
            </a>
        </div>
    

    <div class="article-details">
    
    <header class="article-category">
        
            <a href="/categories/%E7%AE%97%E6%B3%95/" >
                算法
            </a>
        
    </header>
    

    <h2 class="article-title">
        <a href="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/">排序算法（一）</a>
    </h2>

    

    
    <footer class="article-time">
        
            <div>
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-calendar-time" width="56" height="56" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <path d="M11.795 21h-6.795a2 2 0 0 1 -2 -2v-12a2 2 0 0 1 2 -2h12a2 2 0 0 1 2 2v4" />
  <circle cx="18" cy="18" r="4" />
  <path d="M15 3v4" />
  <path d="M7 3v4" />
  <path d="M3 11h16" />
  <path d="M18 16.496v1.504l1 1" />
</svg>
                <time class="article-time--published">Jan 10, 2022</time>
            </div>
        

        
            <div>
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-clock" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="12" cy="12" r="9" />
  <polyline points="12 7 12 12 15 15" />
</svg>



                <time class="article-time--reading">
                    1 minute read
                </time>
            </div>
        
    </footer>
    
</div>
</header>

    <section class="article-content">
    <h2 id="一什么是排序算法">一、什么是排序算法</h2>
<p>​		所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。</p>
<h2 id="二排序的稳定性">二、排序的稳定性</h2>
<p><strong>在了解排序算法之前，我们先了解下排序的稳定性：</strong>
所谓的排序稳定性是指在排序的前后，元素的相对次序是否发生改变。若相对次序发生改变，那么证明该排序算法是不稳定的。
举个🌰，数组a的值为[1,5,3,<strong>5</strong>,4]，我们可以看到排序前加粗的<strong>5</strong>排在前一个未加粗的5后面，经过某种排序算法后数组a的值为[1,3,4,<strong>5</strong>,5]，此时加粗的<strong>5</strong>排在了未加粗的5前面，这样元素的相对次序就发生了改变，所以这种排序算法的稳定性就是不稳定的。</p>
<h2 id="三基础的排序算法">三、基础的排序算法</h2>
<h3 id="1冒泡排序">1.冒泡排序</h3>
<p>​		冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。<strong>简单来说就是元素间两两相比较，当比对到数组中最后一个元素时，最大|最小的元素就落到数组中最后一个位置，再不断的重复此过程最终数组就变得有序了。</strong></p>
<h4 id="动图演示">动图演示</h4>
<p>(点击查看)</p>
<p><figure 
	
		class="gallery-image" 
		style="
			flex-grow: 321; 
			flex-basis: 771px"
	>
	<a href="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E5%86%92%E6%B3%A1.gif" data-size="826x257">
		<img src="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E5%86%92%E6%B3%A1.gif"
			width="826"
			height="257"
			srcset="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E5%86%92%E6%B3%A1_hu7ad85e0fc2bc180bbafbd2e02238cfe7_466890_480x0_resize_box.gif 480w, /post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E5%86%92%E6%B3%A1_hu7ad85e0fc2bc180bbafbd2e02238cfe7_466890_1024x0_resize_box.gif 1024w"
			loading="lazy"
			>
	</a>
	
</figure></p>
<h4 id="代码实现">代码实现</h4>
<p>先定义一个用于交换的方法，以便复用：</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-java" data-lang="java"><span style="color:#66d9ef">public</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">swap</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> nums<span style="color:#f92672">,</span><span style="color:#66d9ef">int</span> i<span style="color:#f92672">,</span><span style="color:#66d9ef">int</span> j<span style="color:#f92672">){</span>
       <span style="color:#66d9ef">int</span> temp<span style="color:#f92672">=</span>nums<span style="color:#f92672">[</span>i<span style="color:#f92672">];</span>
       nums<span style="color:#f92672">[</span>i<span style="color:#f92672">]=</span>nums<span style="color:#f92672">[</span>j<span style="color:#f92672">];</span>
       nums<span style="color:#f92672">[</span>j<span style="color:#f92672">]=</span>temp<span style="color:#f92672">;</span>
    <span style="color:#f92672">}</span>
</code></pre></div><p>冒泡排序：</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-java" data-lang="java"><span style="color:#75715e">//冒泡排序,时间复杂度O(n²),具有稳定性
</span><span style="color:#75715e"></span>    <span style="color:#66d9ef">public</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">bubbleSort</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> nums<span style="color:#f92672">){</span>
        <span style="color:#66d9ef">int</span> len<span style="color:#f92672">=</span>nums<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span><span style="color:#f92672">-</span>1<span style="color:#f92672">;</span>
        <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> i<span style="color:#f92672">=</span>len<span style="color:#f92672">;</span>i<span style="color:#f92672">&gt;</span>0<span style="color:#f92672">;</span>i<span style="color:#f92672">--){</span>
            <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> j <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span> j <span style="color:#f92672">&lt;</span>i <span style="color:#f92672">;</span> j<span style="color:#f92672">++)</span> <span style="color:#f92672">{</span>
                <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>nums<span style="color:#f92672">[</span>j<span style="color:#f92672">]&gt;</span>nums<span style="color:#f92672">[</span>j<span style="color:#f92672">+</span>1<span style="color:#f92672">]){</span>
                  swap<span style="color:#f92672">(</span>nums<span style="color:#f92672">,</span>j<span style="color:#f92672">,</span>j<span style="color:#f92672">+</span>1<span style="color:#f92672">);</span>
                <span style="color:#f92672">}</span>
            <span style="color:#f92672">}</span>
        <span style="color:#f92672">}</span>
    <span style="color:#f92672">}</span>
</code></pre></div><p>冒泡排序的时间复杂度为O(n²)，又因为再对比时相等的值不会交换，所以具有稳定性。</p>
<h3 id="2选择排序">2.选择排序</h3>
<h4 id="算法描述">算法描述</h4>
<p>​		选择排序是一种简单直观的排序算法，它也是一种交换排序算法，和冒泡排序有一定的相似度，可以认为选择排序是冒泡排序的一种改进。<strong>选择排序的原理就是：从未排序的数组中找到数组中的最大（小）值，放到未排序数组的起始位置，重复此过程最终整个数组就变成了一个有序数组</strong>。</p>
<h4 id="动图演示-1">动图演示</h4>
<p>(点击查看)</p>
<p><figure 
	
		class="gallery-image" 
		style="
			flex-grow: 327; 
			flex-basis: 784px"
	>
	<a href="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E9%80%89%E6%8B%A9.gif" data-size="811x248">
		<img src="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E9%80%89%E6%8B%A9.gif"
			width="811"
			height="248"
			srcset="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E9%80%89%E6%8B%A9_hu44548e6b3dec389d786ce5dde322fa72_311395_480x0_resize_box.gif 480w, /post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E9%80%89%E6%8B%A9_hu44548e6b3dec389d786ce5dde322fa72_311395_1024x0_resize_box.gif 1024w"
			loading="lazy"
			>
	</a>
	
</figure></p>
<h4 id="代码实现-1">代码实现</h4>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-java" data-lang="java"><span style="color:#75715e">//选择排序,时间复杂度O(n²),不具有稳定性
</span><span style="color:#75715e"></span>    <span style="color:#66d9ef">public</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">selectSort</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> nums<span style="color:#f92672">){</span>
        <span style="color:#66d9ef">int</span> len<span style="color:#f92672">=</span>nums<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span><span style="color:#f92672">-</span>1<span style="color:#f92672">;</span>
        <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> i <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span> i <span style="color:#f92672">&lt;=</span>len <span style="color:#f92672">;</span> i<span style="color:#f92672">++)</span> <span style="color:#f92672">{</span>
            <span style="color:#66d9ef">int</span> minIndex<span style="color:#f92672">=</span>i<span style="color:#f92672">;</span>
            <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> j <span style="color:#f92672">=</span> i<span style="color:#f92672">+</span>1<span style="color:#f92672">;</span> j <span style="color:#f92672">&lt;=</span>len <span style="color:#f92672">;</span> j<span style="color:#f92672">++)</span> <span style="color:#f92672">{</span>
                <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>nums<span style="color:#f92672">[</span>j<span style="color:#f92672">]&lt;</span>nums<span style="color:#f92672">[</span>minIndex<span style="color:#f92672">]){</span>
                    minIndex<span style="color:#f92672">=</span>j<span style="color:#f92672">;</span>
                <span style="color:#f92672">}</span>
            <span style="color:#f92672">}</span>
            swap<span style="color:#f92672">(</span>nums<span style="color:#f92672">,</span>i<span style="color:#f92672">,</span>minIndex<span style="color:#f92672">);</span>
        <span style="color:#f92672">}</span>
    <span style="color:#f92672">}</span>
</code></pre></div><p>​		通过选择排序的代码我们可以发现，选择排序相比于冒泡排序减少了核心的交换次数，有着一定的优化。但总体来讲选择排序的时间复杂度总体来说也是<code>O(n²)</code>，选择排序不具备排序的稳定性。</p>
<h3 id="3插入排序">3.插入排序</h3>
<h4 id="算法描述-1">算法描述</h4>
<p>​		插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。<strong>简单来说，就是从左到右去维护一个稳定的区间，再不断的根据后续的元素插入到区间内的对应位置，最终数组整体的元素就变得有序了。</strong></p>
<h4 id="动图演示-2">动图演示</h4>
<p>(点击查看)</p>
<p><figure 
	
		class="gallery-image" 
		style="
			flex-grow: 160; 
			flex-basis: 385px"
	>
	<a href="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E6%8F%92%E5%85%A5.gif" data-size="720x448">
		<img src="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E6%8F%92%E5%85%A5.gif"
			width="720"
			height="448"
			srcset="/post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E6%8F%92%E5%85%A5_hu1e7629daa5492fb29d886f96cbcc5d4b_521690_480x0_resize_box.gif 480w, /post/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E6%8F%92%E5%85%A5_hu1e7629daa5492fb29d886f96cbcc5d4b_521690_1024x0_resize_box.gif 1024w"
			loading="lazy"
			>
	</a>
	
</figure></p>
<h4 id="代码演示">代码演示</h4>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-java" data-lang="java"><span style="color:#75715e">//插入排序，时间复杂度O(n²)，具备稳定性，且常数项最小
</span><span style="color:#75715e"></span>    <span style="color:#66d9ef">public</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">insertSort</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> nums<span style="color:#f92672">){</span>
        <span style="color:#66d9ef">int</span> len<span style="color:#f92672">=</span>nums<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span><span style="color:#f92672">-</span>1<span style="color:#f92672">;</span>
        <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> i <span style="color:#f92672">=</span> 1<span style="color:#f92672">;</span> i <span style="color:#f92672">&lt;=</span>len<span style="color:#f92672">;</span> i<span style="color:#f92672">++)</span> <span style="color:#f92672">{</span>
            <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> j <span style="color:#f92672">=</span> i<span style="color:#f92672">-</span>1<span style="color:#f92672">;</span> j<span style="color:#f92672">&gt;=</span>0 <span style="color:#f92672">;</span> j<span style="color:#f92672">--)</span> <span style="color:#f92672">{</span>
                <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>nums<span style="color:#f92672">[</span>j<span style="color:#f92672">+</span>1<span style="color:#f92672">]&lt;</span>nums<span style="color:#f92672">[</span>j<span style="color:#f92672">]){</span>
                swap<span style="color:#f92672">(</span>nums<span style="color:#f92672">,</span>j<span style="color:#f92672">+</span>1<span style="color:#f92672">,</span>j<span style="color:#f92672">);</span>
                <span style="color:#f92672">}</span>
            <span style="color:#f92672">}</span>
        <span style="color:#f92672">}</span>
    <span style="color:#f92672">}</span>
</code></pre></div><p>虽然插入排序的时间复杂度也为<code>O(n²)</code>，但它的常数项确实最小的，它也是冒泡排序的一种改良，我们可以发现这种算法减少了无用的比较和交换，当数据量小的时候常数项也决定着排序算法的效率。</p>
<p>如，在JDK 7 java.util.Arrays所用的<code>sort</code>方法的实现中，当待排数组长度小于47时，会使用插入排序。插入排序具备排序的稳定性。</p>

</section>


    <footer class="article-footer">
    
    <section class="article-tags">
        
            <a href="/tags/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/">排序算法</a>
        
    </section>


    </footer>


    
</article>

    <aside class="related-contents--wrapper">
    
    
</aside>

     
    
        
    

    <script src="https://s3.pstatp.com/cdn/expire-1-M/jquery/3.2.1/jquery.min.js"></script>
        <script>
        function color_tags() {
            var colorArr = ["#428BCA", "#AEDCAE", "#ECA9A7", "#DA99FF", "#FFB380", "#D9B999"];
            $('.tagCloud-tags a').each(function () {
                try {
                    tagsColor = colorArr[Math.floor(Math.random() * colorArr.length)];
                    $(this).css("background", tagsColor); 
                }
                catch (err) { }
            });
        }

        $(document).ready(function () {
            color_tags()
        });
    </script>
    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

<footer class="site-footer">
<span id="busuanzi_container_site_uv">
    本站总访问量<span id="busuanzi_value_site_uv"></span>次
</span>
    <section class="copyright">
        &copy; 
        
        2022zp妙妙屋·<i class="fas fa-bell"></i> <a id="days">0</a>Days<br>共叭叭了 3682字·共 16篇文章</br><span><p>
    </section>
    <div style="width:300px;margin:0 auto; padding:20px 0;">
    <a href="https://beian.miit.gov.cn/，" rel="external nofollow" target="_blank"><p style="float:left;height:20px;line-height:20px;margin: 0px 0px 0px 25px; color:#939393;">京ICP备2022000201号-1</p></a></span>
		 		<a target="_blank" href="http://www.beian.gov.cn/portal/registerSystemInfo?recordcode=11011102001825" style="display:inline-block;text-decoration:none;height:20px;line-height:20px;"><img src="/beian.png" style="float:left;"/><p style="float:left;height:20px;line-height:20px;margin: 0px 0px 0px 5px; color:#939393;">京公网安备 11011102001825号</p></a>
	</div>
    <section class="powerby">
        Built with <a href="https://gohugo.io/" target="_blank" rel="noopener">Hugo</a> <br />
        Theme <b><a href="https://github.com/CaiJimmy/hugo-theme-stack" target="_blank" rel="noopener" data-version="3.5.0">Stack</a></b> designed by <a href="www.zpzp.vip" target="_blank" rel="noopener">ZP</a>
    </section>
</footer>



    
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

    
    <div class="pswp__bg"></div>

    
    <div class="pswp__scroll-wrap">

        
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>

        
        <div class="pswp__ui pswp__ui--hidden">

            <div class="pswp__top-bar">

                

                <div class="pswp__counter"></div>

                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

                <button class="pswp__button pswp__button--share" title="Share"></button>

                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

                
                
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                        <div class="pswp__preloader__cut">
                            <div class="pswp__preloader__donut"></div>
                        </div>
                    </div>
                </div>
            </div>

            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div>
            </div>

            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>

            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>

            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>

        </div>

    </div>

</div><script 
                src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js"integrity="sha256-ePwmChbbvXbsO02lbM3HoHbSHTHFAeChekF1xKJdleo="crossorigin="anonymous"
                defer="true"
                >
            </script><script 
                src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js"integrity="sha256-UKkzOn/w1mBxRmLLGrSeyB4e1xbrp4xylgAWb3M42pU="crossorigin="anonymous"
                defer="true"
                >
            </script><link 
                rel="stylesheet" 
                href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.css"integrity="sha256-c0uckgykQ9v5k&#43;IqViZOZKc47Jn7KQil4/MP3ySA3F8="crossorigin="anonymous"
            ><link 
                rel="stylesheet" 
                href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.css"integrity="sha256-SBLU4vv6CA6lHsZ1XyTdhyjJxCjPif/TRkjnsyGAGnE="crossorigin="anonymous"
            >

            </main>
    
        <aside class="sidebar right-sidebar sticky">
            <section class="widget archives">
                <div class="widget-icon">
                    <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-hash" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <line x1="5" y1="9" x2="19" y2="9" />
  <line x1="5" y1="15" x2="19" y2="15" />
  <line x1="11" y1="4" x2="7" y2="20" />
  <line x1="17" y1="4" x2="13" y2="20" />
</svg>



                </div>
                <h2 class="widget-title section-title">Table of contents</h2>
                
                <div class="widget--toc">
                    <nav id="TableOfContents">
  <ul>
    <li><a href="#一什么是排序算法">一、什么是排序算法</a></li>
    <li><a href="#二排序的稳定性">二、排序的稳定性</a></li>
    <li><a href="#三基础的排序算法">三、基础的排序算法</a>
      <ul>
        <li><a href="#1冒泡排序">1.冒泡排序</a></li>
        <li><a href="#2选择排序">2.选择排序</a></li>
        <li><a href="#3插入排序">3.插入排序</a></li>
      </ul>
    </li>
  </ul>
</nav>
                </div>
            </section>
        </aside>
    

        </div>
        <script 
                src="https://cdn.jsdelivr.net/npm/node-vibrant@3.1.5/dist/vibrant.min.js"integrity="sha256-5NovOZc4iwiAWTYIFiIM7DxKUXKWvpVEuMEPLzcm5/g="crossorigin="anonymous"
                defer="false"
                >
            </script><script type="text/javascript" src="/ts/main.js" defer></script>
<script>
    (function () {
        const customFont = document.createElement('link');
        customFont.href = "https://fonts.googleapis.com/css2?family=Lato:wght@300;400;700&display=swap";

        customFont.type = "text/css";
        customFont.rel = "stylesheet";

        document.head.appendChild(customFont);
    }());
</script>

<script
    src="https://cdn.jsdelivr.net/gh/zhixuan2333/gh-blog@v0.1.0/js/ribbon.min.js"
    integrity="sha384-UEK8ZiP3VgFNP8KnKMKDmd4pAUAOJ59Y2Jo3ED2Z5qKQf6HLHovMxq7Beb9CLPUe"
    crossorigin="anonymous"
    size="300"
    alpha="0.6"
    zindex="-1"
    defer
></script>
<script
    src="https://cdn.jsdelivr.net/gh/zhixuan2333/gh-blog@v0.1.0/js/nprogress.min.js"
    integrity="sha384-bHDlAEUFxsRI7JfULv3DTpL2IXbbgn4JHQJibgo5iiXSK6Iu8muwqHANhun74Cqg"
    crossorigin="anonymous"
></script>
<link
    rel="stylesheet"
    href="https://cdn.jsdelivr.net/gh/zhixuan2333/gh-blog@v0.1.0/css/nprogress.css"
    integrity="sha384-KJyhr2syt5+4M9Pz5dipCvTrtvOmLk/olWVdfhAp858UCa64Ia5GFpTN7+G4BWpE"
    crossorigin="anonymous"
/>
<script src="/js/snow.js"></script>
<script>
    NProgress.start();
    document.addEventListener("readystatechange", () => {
        if (document.readyState === "interactive") NProgress.inc(0.8);
        if (document.readyState === "complete") NProgress.done();
    });
</script>

    </body>
</html>
